#include "merge_sort.h"
#include "benchmark.h"
#include "genlib.h"

/* Private function prototypes */
static void merge(int array[], int arr1[], int n1, int arr2[], int n2);
static int *CopySubArray(int array[], int start, int n);

void mergeSort(int array[], int n) {
	int n1, n2, *arr1, *arr2;

	if (n <= 1) return;
	n1 = n / 2;
	n2 = n - n1;
	arr1 = CopySubArray(array, 0, n1);
	arr2 = CopySubArray(array, n1, n2);
	mergeSort(arr1, n1);
	mergeSort(arr2, n2);
	merge(array, arr1, n1, arr2, n2);
	FreeBlock(arr1);
	FreeBlock(arr2);
}

static void merge(int array[], int arr1[], int n1, int arr2[], int n2) {
	int p, p1, p2;
	p = p1 = p2 = 0;
	
	while (p1 < n1 && p2 < n2) {
		if (arr1[p1] < arr2[p2]) {
			array[p++] = arr1[p1++];
		} else {
			array[p++] = arr2[p2++];
		}
	}
	while (p1 < n1) array[p++] = arr1[p1++];
	while (p2 < n2) array[p++] = arr2[p2++];
}

static int *CopySubArray(int array[], int start, int n) {
	int i, *result;

	result = NewArray(n, int);
	for (i=0; i<n; i++) {
		benchAddOperation(benchmark);
		result[i] = array[start + i];
	}
	return (result);
}